from typing import List

# 1.输入一个数组和一个数字，在数组中查找两个数，使得他们的和与输入的数字差绝对值最小，
# 比如输入是[8，3，6，1]和13，输出是8和6


def func(nums: List, target: int):
    if len(nums) < 2:
        return
    t = float('inf')
    a, b = 0, 0
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if abs(nums[i]+nums[j]-target) < t:
                t = abs(nums[i]+nums[j]-target)
                a, b = i, j
    return nums[a], nums[b]


# 2. 给定两个有序（从小到大）整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
# 说明:
# 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
# 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素)。
# 请写出你认为时间和空间复杂度最低的代码。
def merge(nums1: List, nums2: List):
    temp = []
    while len(nums1) > 0 and len(nums2) > 0:
        if nums1[0] <= nums2[0]:
            temp.append(nums1.pop(0))
        else:
            temp.append(nums2.pop(0))
    while len(nums1) > 0:
        temp.append(nums1.pop(0))
    while len(nums2) > 0:
        temp.append(nums2.pop(0))
    nums1 = temp
    return nums1


def merge1(nums1: List, nums2: List):
    if not nums2:
        return nums1
    if not nums1:
        nums1 = nums2
        return nums1
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] > nums2[j]:
            nums1.insert(i, nums2[j])
            j += 1
        i += 1
    if j < len(nums2):
        nums1.extend(nums2[j:])
    return nums1


"""
3.(sql)给定一个二叉树的表格，包含两列：Node 和 Parent，Node表示二叉树的节点值，
Parent是Node的父节点。
表名为BST：
Column	Type
Node	Integer
Parent	Integer
我们希望能找到二叉树每个节点类型，并按照大小排序。按如下方式输出结果:
当节点是二叉树的根节点，输出Root
当节点是叶子节点时，输出Leaf
当节点两者都不是时，输出Inner
输入样例
Node    Parent
1   2
3   2
6   8
9   8
2   5
8   5
5   null
输出样例
1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf
二叉树样例：
    5
  2   8
1  3 6  9

思路：

Root--无父节点:
SELECT BST.Node FROM BST WHERE BST.Parent==null

Inner--既有父节点，又有子节点:
SELECT BST.Node FROM BST WHERE BST.Parent!=null
UNION
SELECT BST.Parent FROM BST

Leaf--只有父节点，没有子节点:
SELECT BST.Node FROM BST WHERE BST.Parent!=null AND BST.Node NOT IN(SELECT BST.Parent FROM BST WHERE BST.Parent!=null)

整合输出：
"""
if __name__ == '__main__':
    print(merge1([1, 3, 5], [0, 1, 2, 3, 4, 5, 6, 7, 8]))
